//给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, 
//ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 
//
// 说明：你不能倾斜容器，且 n 的值至少为 2。 
//
// 
//
// 
//
// 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。 
//
// 
//
// 示例： 
//
// 输入：[1,8,6,2,5,4,8,3,7]
//输出：49 
// Related Topics 数组 双指针

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：盛最多水的容器
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P11_ContainerWithMostWater {

    public static void main(String[] args) {
        Solution solution = new P11_ContainerWithMostWater().new Solution();
        int[] array = MyUtil.createRandomArray(15, 1, 15);
        array = new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7};
        int area = solution.maxArea(array);
        MyUtil.print(area);
    }

    //    leetcode submit region begin(Prohibit modification and deletion)
    ///**
    // * 暴力求解
    // * 时间复杂度 O(n^2)
    // */
    //class Solution {
    //    public int maxArea(int[] nums) {
    //        int area = 0;
    //        for (int i = 0; i < nums.length - 1; i++) {
    //            for (int j = i + 1; j < nums.length; j++) {
    //                area = Math.max((j - i) * Math.min(nums[i], nums[j]), area);
    //            }
    //        }
    //        return area;
    //    }
    //}

    /**
     * 双指针
     * 时间复杂度 O(n)
     */
    class Solution {
        public int maxArea(int[] nums) {
            int i = 0, j = nums.length - 1, area = 0;
            while (i < j) {
                area = Math.max(area, (j - i) * (nums[i] < nums[j] ? nums[i++] : nums[j--]));
            }
            return area;
        }
    }
    //    leetcode submit region end(Prohibit modification and deletion)

}
